'''
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

 

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:

Input: nums = []
Output: []
Example 3:

Input: nums = [0]
Output: []
 

Constraints:

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

'''

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        list1 =[]
        
        #对数组进行排序、
        nums.sort()
        
        #i为角标，a为元素
        for i ,a in enumerate(nums):
            #从第二个元素开始，如果和前一个元素一样则跳过
            if i>0 and a==nums[i-1]:
                continue
            
            #从当前元素的后一个l，和最后的一个元素r，进行求和
            
            l,r =i+1,len(nums)-1
            while(l<r):
                su = a+ nums[l]+nums[r]
                #当大于0，右边的往前移动一格
                if su>0:
                     r -=1
                #当小于0，左边的往后移动一格
                elif su<0:
                    l  +=1
                else:
                    #等于0
                    list1.append([a,nums[l],nums[r]])
                    #判断下一个元素是否和当前元素一样
                    l +=1
                    #一样的话，则进行跳过
                    while nums[l]==nums[l-1] and l<r:
                        l +=1
                    
        return list1